package org.chnxi.leetcode.problems.ques17;

import java.util.*;

/**
 * 电话号码的字母组合 - 使用递归方式
 * 执行用时 :1 ms, 在所有 Java 提交中击败了90.87%的用户
 * 内存消耗 :38.8 MB, 在所有 Java 提交中击败了5.17%的用户
 */
public class Simple01 {

    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));

        System.out.println(letterCombinations("234"));

        System.out.println(letterCombinations("023"));

        System.out.println(letterCombinations("230"));

        System.out.println(letterCombinations("203"));

    }

    //对键盘数字建立字典值 K - 键盘数字， V - 对应的字符串列表
    static Map<Character , List<String>> dicts = new HashMap<>();

    static {
        dicts.put('2' , Arrays.asList("a", "b", "c"));
        dicts.put('3' , Arrays.asList("d", "e", "f"));
        dicts.put('4' , Arrays.asList("g", "h", "i"));
        dicts.put('5' , Arrays.asList("j", "k", "l"));
        dicts.put('6' , Arrays.asList("m", "n", "o"));
        dicts.put('7' , Arrays.asList("p", "q", "r", "s"));
        dicts.put('8' , Arrays.asList("t", "u", "v"));
        dicts.put('9' , Arrays.asList("w", "x", "y", "z"));
    }

    public static List<String> letterCombinations(String digits) {

        List<String> result = new ArrayList<>();

        //安全性检查
        if(digits == null || (digits = digits.trim()).length() < 1){
            return result;
        }

        parse(digits.toCharArray() , 0 , new StringBuilder() , result);

        return result;
    }

    /**
     * 使用递归的方式进行字符串拼接
     * @param chars
     * @param idx
     * @param current
     * @param result
     */
    private static void parse(char[] chars , int idx , StringBuilder current, List<String> result){

        //已经拼接到字符串最后一位索引+1，需要填充结果，退出方法
        if(idx > chars.length-1){
            result.add(current.toString());
            return;
        }

        //获取字符串对应的V
        List<String> dict = dicts.get(chars[idx]);

        //去除键盘中0、1、*、#不存在字母对应的情况
        //不需要处理当前字符，直接处理下一个
        if(dict == null){
            parse(chars , ++idx, current, result);
        }else{
            //循环拼接当前字符
            for (int i = 0; i<dict.size(); i++){
                //构造新的字符拼接
                StringBuilder sb = new StringBuilder(current.toString());
                sb.append(dict.get(i));
                //拼接后，原字符串还有后续内容，继续向后拼接
                if(idx < chars.length){
                    parse(chars , idx + 1  , sb , result);
                }
            }
        }

    }

}
